package com.test.daily.leetcode.y2022.m07.day0723.v03;

import java.util.HashMap;
import java.util.Stack;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/23 下午 04:44
 * @version: 1.0
 */
public class Solution {
    public static class Node<V> {
        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public static class UnionFind<V> {
        HashMap<V, Node> nodes;
        HashMap<Node, Node> fatherMap;
        HashMap<Node, Integer> sizeMap;

        public UnionFind(V[] arr) {
            for (int i = 0; i < arr.length; i++) {
                Node node = new Node(arr[i]);
                nodes.put(arr[i], node);
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public Node findFather(Node node) {
            Stack<Node> path = new Stack<>();
            if (node != fatherMap.get(node)) {
                path.push(node);
            }
            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), node);
            }
            return node;
        }

        public boolean isSameFather(V o1, V o2) {
            Node n1 = nodes.get(o1);
            Node n2 = nodes.get(o2);
            return findFather(n1) == findFather(n2);
        }

        public int size() {
            return sizeMap.size();
        }

        public void union(V v1, V v2) {
            Node o1 = nodes.get(v1);
            Node o2 = nodes.get(v2);
            if (findFather(o1) != findFather(o2)) {
                int o1Size = sizeMap.get(o1);
                int o2Size = sizeMap.get(o2);
                Node big = o1Size > o2Size ? o1 : o2;
                Node small = big == o1 ? o2 : o1;
                fatherMap.put(small, big);
                sizeMap.put(big, o1Size + o2Size + 1);
                sizeMap.remove(small);
            }
        }
    }
}
